|
In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that: (1). no adjacent vertices have the same color; (2). no adjacent edges have the same color; and (3). no edge and its endvertices are assigned the same color. In 2005, Zhang et al.〔Zhang 2005.〕 added a restriction to the definition of total coloring and proposed a new type of coloring defined as follows. Let ''G'' = (''V'',''E'') be a simple graph endowed with a total coloring φ, and let ''u'' be a vertex of ''G''. The set of colors that occurs in the vertex ''u'' is defined as ''C''(''u'') = ∪ . Two vertices ''u'',''v'' ∈ ''V''(''G'') are distinguishable if their color-sets are distinct, i.e., ''C''(''u'') ≠ ''C''(''v''). In graph theory, a total coloring is an adjacent-vertex-distinguishing-total-coloring (AVD-total-coloring) if it has the following additional property: (4). for every two adjacent vertices ''u'',''v'' of a graph ''G'', their colors-sets are distinct from each other, i.e., ''C''(''u'') ≠ ''C''(''v''). The adjacent-vertex-distinguishing-total-chromatic number ''χ''at(''G'') of a graph ''G'' is the least number of colors needed in an AVD-total-coloring of ''G''. The following lower bound for the AVD-total chromatic number can be obtained from the definition of AVD-total-coloring: If a simple graph ''G'' has two adjacent vertices of maximum degree, then ''χ''''at''(''G'') ≥ Δ(''G'') + 2.〔Zhang 2005, p. 290.〕 Otherwise, if a simple graph ''G'' does not have two adjacent vertices of maximum degree, then ''χ''''at''(''G'') ≥ Δ(''G'') + 1. In 2005, Zhang et al. determined the AVD-total-chromatic number for some classes of graphs, and based in their results they conjectured the following. AVD-Total-Coloring Conjecture. (Zhang et al.〔Zhang 2005, p. 299.〕) :''χ''''at''(''G'') ≤ Δ(''G'') + 3. The AVD-Total-Coloring Conjecture is known to hold for some classes of graphs, such as complete graphs,〔Hulgan 2009, p. 2.〕 graphs with Δ=3,〔Hulgan 2009, p. 2.〕〔Chen 2008.〕 and all bipartite graphs.〔Zhang 2005.〕 In 2012, Huang et al.〔Huang2012〕 showed that ''χ''''at''(''G'') ≤ 2Δ(''G'') for any simple graph ''G'' with maximum degree Δ(''G'') > 2. In 2014, Papaioannou and Raftopoulou〔Papaioannou2014〕 described an algorithmic procedure that gives a 7-AVD-total-colouring for any 4-regular graph. == Notes == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Adjacent-vertex-distinguishing-total coloring」の詳細全文を読む スポンサード リンク
|